package gold.digger;

import java.util.*;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC673 {
    public long startExecuteTime = System.currentTimeMillis();


    /*
     * @param 此题目参考了别人代码，自己只理解思想
     * 经典解法，每日一看
     * 根据官方题解Java版本动态规划的通俗的解读：

        数组lengths[i]：其值表示包含第i个元素nums[i]且以其为结尾的最长递增子序列的长度。
        数组counts[i]: 其值表示以i为结尾的，且是所能得到的以nums[i]结尾的最长递增子序列长度的可能组合的个数。这里要注意每一个元素，可能的个数至少为1，因为最短也会包含它自己。
        根据题解，要注意双层for循环 j 在外层，i 在内层。
        如果 nums[i] < nums[j]，也就是说 j 〉i 时 nums[j] 比nums[i]大，也就是此时可以将nums[j] 添加到以nums[i]结尾的最长递增子序列的末尾。
        此时，如果以nums[i]结尾的最长递增子序列的长度lengths[i] 是大于等于以nums[j]结尾的最长递增子序列的长度lengths[j] 的，那么此时要更新以nums[j]结尾的最长递增子序列的长度，即lengths[j] = lengths[i] + 1，并且可以知道counts[j] = counts[i]；
        否则，如果以nums[i]结尾的最长递增子序列的长度lengths[i] 是小于以nums[j]结尾的最长递增子序列的长度lengths[j] 的，且此时lengths[i] + 1 == lengths[j]，即以nums[i]结尾的最长递增子序列加上nums[j]后的长度，刚好等于lengths[j]，那么此时所有以nums[i]结尾的最长递增子序列加上1后都符合要求，所以counts[j] += counts[i]；
        最后，根据数组lengths找到最长递增子序列的长度时的nums数组下标 i ，然后根据counts数组，获取个数即是答案。
     * @return:
     */
    class Solution {
        public int findNumberOfLIS(int[] nums) {
            int N = nums.length;
            if (N <= 1) return N;
            int[] lengths = new int[N]; //lengths[i] = length of longest ending in nums[i]
            int[] counts = new int[N]; //count[i] = number of longest ending in nums[i]
            Arrays.fill(counts, 1);

            for (int j = 0; j < N; ++j) {
                for (int i = 0; i < j; ++i)
                    if (nums[i] < nums[j]) {
                        if (lengths[i] >= lengths[j]) {
                            lengths[j] = lengths[i] + 1;
                            counts[j] = counts[i];
                        } else if (lengths[i] + 1 == lengths[j]) {
                            counts[j] += counts[i];
                        }
                    }
            }

            int longest = 0, ans = 0;
            for (int length : lengths) {
                longest = Math.max(longest, length);
            }
            for (int i = 0; i < N; ++i) {
                if (lengths[i] == longest) {
                    ans += counts[i];
                }
            }
            return ans;
        }
    }


    //    线段树的做法. 根据不知所云的官方题解自行思考.
//
//            在一个节点中, 使用两个整型L, R存储一个区间信息[L, R]. 这个区间表示"递增子序列的最大元素(以下称为end))允许的存在范围"; 使用一个整型len存储满足L≤end≤R条件的子序列的最大长度, 使用一个整型cnt存储达到最大长度的子序列的数目(对示例1: [1,3,5,4,7], 当完成对输入的遍历后, 设线段树内某个节点的[L, R]是[6, 8], 那么它的len为4, cnt为2.).
//    对于树叶, 总是有L == R. 对于其他节点, L < R代表一个区间. 根节点的[L, R]可视作(-∞, +∞), 也可视作[输入的最小值, 输出的最小值], 根据前述定义, 根节点的len表示"end落在nums范围内的全部子序列"的最大长度, 也即题设所描述的最长递增子序列, 而cnt就是所需的"个数". 顺带一提, 官方题解的len描述的真的是"长度", 例如序列1,5,6由"3"个数字构成, 如果把数字想象成点, 那么连接3个点的线段则是2条, 所以"长度"是"2", 这也是官方题解的代码中, 新Value对象的len初始化为0的缘故. 不过len的精确定义并不那么重要, 它只要能反映出长度的"相对大小", 就可以帮我们定位到长度最大的子序列, 所以只需要代码内len的定义保持一致即可.
//            接下来要考虑线段树的生成:
//    自底向上的生成方式, 可考虑首先对输入离散化处理--建立一份输入的拷贝, 对这份拷贝执行排序, 从而获取输入的每个元素在排序后的索引(这里将用到二分查找). 之后遍历输入, 因为已知各元素的"排序索引", 因此使用数组建立线段树的话, 可以明确知道自底向上更新线段树的位置.
//            自顶向下的生成方式, 也即官方题解所描述的方式: 首先获取输入的最大/最小值, 作为[L, R]信息来建立根 节点; 之后遍历输入(记当前读取的数值为key), 先通过query例程基于当前的树获取Value值(即, 基于nums 已读入的元素, 获取end < key的最长子序列的信息, 这一步利用了线段树的性质, 通过merge例程统计了那些 R < key的线段/节点), 然后递归地通过二分法搜索/创建子节点, 直到抵达/创建一个区间信息为[key, key] 的树叶. 这种构建方式将需要使用链表, 而不适合数组.
//            官方题解的一个明显可优化的方式同样是对输入进行离散化. 最极端的情形, L == INT_MIN 而 R == INT_MAX, 则每次操作都需要搜索32层.
    class Solution_Segment_Tree {

        class Node {
            //每个节点挂载了，这个节点的范围[range_left,range_right]
            int range_left, range_right;
            //以及它的关系节点，左右两区间，左边[range_left,mid]，右边[mid+1,range_right]——自行定义的区间划分，保持统一即可
            Node left, right;
            //这个区间范围内的len,count数量，自行定义的数据结构，根据题目所求不同自行设置
            Value val;

            public Node(int start, int end) {
                range_left = start;
                range_right = end;
                left = null;
                right = null;
                val = new Value(0, 1);
            }

            public int getRangeMid() {
                return range_left + (range_right - range_left) / 2;
            }

            public Node getLeft() {
                if (left == null) left = new Node(range_left, getRangeMid());
                return left;
            }

            public Node getRight() {
                if (right == null) right = new Node(getRangeMid() + 1, range_right);
                return right;
            }
        }

        class Value {
            //范围的最大L，默认0
            int length;
            //范围的数量，默认1
            int count;

            public Value(int len, int ct) {
                length = len;
                count = ct;
            }
        }

        //合并左右区间查出来的值，用来更新节点用的
        public Value merge(Value v1, Value v2) {
            //如果左区间的最长长度=右区间的最长长度
            if (v1.length == v2.length) {
                //左边没有找到符合
                if (v1.length == 0) return new Value(0, 1);
                //那结果就是两者相加
                return new Value(v1.length, v1.count + v2.count);
            }
            //取大的值
            return v1.length > v2.length ? v1 : v2;
        }

        public void insert(Node node, int key, Value val) {
            if (node.range_left == node.range_right) {
                //如果是叶子节点，那就直接更新其值并返回
                node.val = merge(val, node.val);
                return;
            } else if (key <= node.getRangeMid()) {
                //这货是左子节点范围的，那就去左子节点那边
                insert(node.getLeft(), key, val);
            } else {
                //这货是右子节点范围的，那就去右子节点那边
                insert(node.getRight(), key, val);
            }
            //递归回来之后，更新父节点的值（因为下面的节点更新过了）
            node.val = merge(node.getLeft().val, node.getRight().val);
        }

        public Value query(Node node, int key) {
            //如果node的right都比key小，那就是你了，node
            if (node.range_right <= key) return node.val;
                //连最左边都比key大，没救了，key你就是无，默认为L是0，count是1
            else if (node.range_left > key) return new Value(0, 1);
                //如果key在node的left-right之间，那就要综合考虑左区间和右区间的结果
            else return merge(query(node.getLeft(), key), query(node.getRight(), key));
        }

        public int findNumberOfLIS(int[] nums) {
            if (nums.length == 0) return 0;
            int min = nums[0], max = nums[0];
            for (int num : nums) {
                //找到值的最小值与最大值，确定根节点的区间————步骤1
                min = Math.min(min, num);
                max = Math.max(max, num);
            }
            //这里，树还没完全建好，只建了一个根，只有调用getLeft,Right才会建后续的节点————步骤2
            Node root = new Node(min, max);
            for (int num : nums) {
                //找到以[min,num-1]范围为尾节点的子序列的，最大长度L，以及个数count————步骤3
                Value v = query(root, num - 1);
                //那么[min,num]区间的值就为[min,num-1]的长度+1，个数继承，插入到表里去————步骤4
                //如果节点本身存在，那么就是更新，不存在，那么就是新增咯————步骤4
                insert(root, num, new Value(v.length + 1, v.count));
            }
            //返回[min,max]的区间的最终结果
            return root.val.count;
        }
    }


    public void run() {
        Solution solution = new Solution();
        List<Integer> list = new ArrayList<>();
        System.out.println(solution.toString());
    }

    public static void main(String[] args) throws Exception {
        LC673 an = new LC673();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
